BZOJ4373 算术天才⑨与等差数列 <线段树+set>

Problem

算术天才⑨与等差数列

Description

算术天才⑨非常喜欢和等差数列玩耍。
有一天，他给了你一个长度为的序列，其中第个数为。
他想考考你，每次他会给出询问，问区间内的数从小到大排序后能否形成公差为的等差数列。
当然，他还会不断修改其中的某一项。
为了不被他鄙视，你必须要快速并正确地回答完所有问题。
注意：只有一个数的数列也是等差数列。

Input

第一行包含两个正整数，分别表示序列的长度和操作的次数。
第二行包含个整数，依次表示序列中的每个数。
接下来行，每行一开始为一个数，
若，则接下来两个整数，表示把修改为。
若，则接下来三个整数，表示一个询问。
在本题中，都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。

Output

输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。

Sample Input

Sample Output

1
2

No
Yes

标签：线段树 set

Solution

线段树判断等差数列，单点修改。

若区间组成等差数列，则一定有：

没有重复的数

其中若存在的情况要单独处理。

对于第一、三个条件，用线段树存储区间即可。
对于第二个条件，需要在外面用维护每个位置的值上一次出现在哪个位置，将这个位置存入线段树中，区间求，若最大值小于，则一定没有重复的数。

注意修改时不止当前位置的前驱会发生变化，所以需要多次更新。

Code

#include <bits/stdc++.h>
#define fir first
#define sec second
#define MAX_N 300000
#define INF 0x3f3f3f3f
#define mid ((s+t)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef set<pii>::iterator IT;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, a[MAX_N+5], lst[MAX_N+5]; set <pii> S;
int mi[MAX_N<<2], mx[MAX_N<<2], pr[MAX_N<<2], cg[MAX_N<<2];
int gcd(int x, int y) {return (~x) ? (y ? gcd(y, x%y) : x) : y;}
void update(int v) {
    mi[v] = min(mi[v<<1], mi[v<<1|1]), mx[v] = max(mx[v<<1], mx[v<<1|1]);
    pr[v] = min(pr[v<<1], pr[v<<1|1]), cg[v] = gcd(cg[v<<1], cg[v<<1|1]);
}
void init(int v, int p) {mi[v] = mx[v] = a[p], pr[v] = lst[p], cg[v] = abs(a[p]-a[p-1]);}
void build(int v, int s, int t) {
    if (s == t) {init(v, s); return;}
    build(v<<1, s, mid);
    build(v<<1|1, mid+1, t);
    update(v);
}
void modify(int v, int s, int t, int p) {
    if (s == t) {init(v, s); return;}
    if (p <= mid) modify(v<<1, s, mid, p);
    if (p >= mid+1) modify(v<<1|1, mid+1, t, p);
    update(v);
}
int query_mi(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return mi[v]; int ret = INF;
    if (l <= mid) ret = min(ret, query_mi(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = min(ret, query_mi(v<<1|1, mid+1, t, l, r));
    return ret;
}
int query_mx(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return mx[v]; int ret = 0;
    if (l <= mid) ret = max(ret, query_mx(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = max(ret, query_mx(v<<1|1, mid+1, t, l, r));
    return ret;
}
int query_pr(int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return pr[v]; int ret = 0;
    if (l <= mid) ret = max(ret, query_pr(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = max(ret, query_pr(v<<1|1, mid+1, t, l, r));
    return ret;
}
int query_cg(int v, int s, int t, int l, int r) {
    if (l > r) return 0;
    if (s >= l && t <= r) return cg[v]; int ret = -1;
    if (l <= mid) ret = gcd(ret, query_cg(v<<1, s, mid, l, r));
    if (r >= mid+1) ret = gcd(ret, query_cg(v<<1|1, mid+1, t, l, r));
    return ret;
}
int main() {
    freopen("1.in", "r", stdin);
    freopen("test.out", "w", stdout);
    read(n), read(m), S.insert(pii(-1, 0)), S.insert(pii(INF, 0));
    for (int i = 1; i <= n; i++) {
        read(a[i]); IT it = S.upper_bound(pii(a[i], i)); it--;
        if ((*it).fir == a[i]) lst[i] = (*it).sec; S.insert(pii(a[i], i));
    }
    build(1, 1, n);
    for (int cnt = 0; m; m--) {
        int opt; read(opt);
        if (opt == 1) {
            int p, x; read(p), read(x), p ^= cnt, x ^= cnt;
            S.erase(pii(a[p], p)); IT it = S.upper_bound(pii(a[p], p));
            if ((*it).fir == a[p]) lst[(*it).sec] = lst[p], modify(1, 1, n, (*it).sec);
            a[p] = x, it = S.upper_bound(pii(a[p], p));
            if ((*it).fir == a[p]) lst[(*it).sec] = p, modify(1, 1, n, (*it).sec);
            it--, lst[p] = (*it).fir == a[p] ? (*it).sec : 0, S.insert(pii(a[p], p));
            modify(1, 1, n, p); if (p < n) modify(1, 1, n, p+1);
        }
        if (opt == 2) {
            int l, r, k; read(l), read(r), read(k), l ^= cnt, r ^= cnt, k ^= cnt;
            int MX = query_mx(1, 1, n, l, r), MI = query_mi(1, 1, n, l, r);
            if (!k) {if (MX == MI) cnt++, puts("Yes"); else puts("No"); continue;}
            if (query_pr(1, 1, n, l, r) >= l || query_cg(1, 1, n, l+1, r)%k) {puts("No"); continue;}
            if (1LL*(MX-MI) != 1LL*(r-l)*k) {puts("No"); continue;} cnt++, puts("Yes");
        }
    }
    return 0;
}